#include "main/utils.h"
using namespace std;

class Solution {
  public:
    void combinationSum(vector<int>& candidates, vector<int>& cur_output, vector<vector<int>>& total_output, int target, int idx) {
      if (idx == candidates.size()) {
        return;
      }

      if (target == 0) {
        total_output.push_back(cur_output);
        return;
      }

      combinationSum(candidates, cur_output, total_output, target, idx + 1);

      if (target - candidates[idx] >= 0) {
        cur_output.push_back(candidates[idx]);
        target -= candidates[idx];
        combinationSum(candidates, cur_output, total_output, target, idx);
        target += candidates[idx];
        cur_output.pop_back();
      }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
      vector<vector<int>> output;
      vector<int> cur_output;
      combinationSum(candidates, cur_output, output, target, 0);
      return output;
    }
};

int main() {
  vector<int> input = {2, 3, 6, 7};
  int target = 7;
  Solution su;
  auto output = su.combinationSum(input, target);
  printVec("output", output);
}
